# 最长连续序列： https://leetcode-cn.com/problems/longest-consecutive-sequence/


# 去重
class Solution:
    def longestConsecutive(self, nums: list) -> int:
        """
            排序解法,排序后去重
        """
        if not nums: return 0
        nums = list(set(nums))
        nums.sort()
        
        i = 1
        rst = 1
        while i < len(nums):
            count = 1
            while i < len(nums) and nums[i] == nums[i-1] + 1:
                count += 1
                i += 1
            rst = max(rst, count)    
            i += 1

        return rst    

# 不去重：
class Solution:
    def longestConsecutive(self, nums: list) -> int:
        """
            排序解法
        """
        if not nums: return 0
        nums.sort()
        
        i = 1
        rst = 1
        while i < len(nums):
            count = 1
            while i < len(nums) and nums[i] >= nums[i-1]:
                if nums[i] == nums[i-1] + 1:
                    count += 1
                    i += 1
                elif nums[i] == nums[i-1]:
                    i += 1
                else:
                    break

            rst = max(rst, count)    
            i += 1

        return rst    

# set hash优化
class Solution:
    def longestConsecutive(self, nums: list) -> int:
        """
            遍历列表中每一个元素，判断以它开头的元素序列是否为最长, 优化掉重复判断的
            当 num - 1 也在集合里，那必然不是最长解
        """
        if not nums: return 0
        
        setN = set(nums)
        rst = 1
        # 关键的优化点： 关键一步！遍历 setN 和 nums ，性能千差万别~ 一个50ms， 一个 接近2000, 可能的原因是hash冲突导致，查找性能降低
        for num in setN:
            if num - 1 in setN: continue

            count = 1
            t = num
            while t + 1 in setN:
                count += 1
                t += 1
            rst = max(rst, count)

        return rst
                

nums = [100,4,200,1,3,2]   

s = Solution()
rst = s.longestConsecutive(nums)
print(rst)
